COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00006 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A91.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 20, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent {RWF:  Draw diagrams]

Let $M$ be a machine $\langle$control, input, other$\rangle$ and $\pi$ a program
for it, using the maximum input repertory.  We construct a program $\pi'$ for
$M$ that simulates $\pi$, using the minimum input repertory.  That is,
$\pi'$ omits {\tt next a}, and never even considers an input operation after
detecting end of file.  The representation relation $\rho = \rho↓1 \cup \rho↓2 
\cup \rho↓3$ is:
$$\displaylines{\langle q . \Lambda, x, s\rangle \rho↓1 \langle q, x, s\rangle\cr
\langle q . a, x, s\rangle \rho↓2 \langle q, ax, s\rangle\cr
\langle q . e, \Lambda, s\rangle \rho↓3 \langle, \Lambda, s\rangle\cr}$$
where $q$ is a control state of $M$, $x$ is a string over the input alphabet,
and $s$ is a state of the other device.

If no instruction appears in the left column, then any instruction in the right
column, for example $\langle q \cdot \Lambda \rightarrow q \cdot a$, $\hbox {scan a}, 
\delta\rangle$, must unconditionally belong to $\pi'$.
$$\eqalign{\alpha'↓{\rm control} & \equiv \alpha↓{\rm control} \circ 
\{\langle q, q \cdot \Lambda \rangle\}\cr
\alpha'↓{\rm input} & \equiv \alpha↓{\rm input}\cr
\alpha↓{\rm other} & \equiv \alpha↓{\rm other}.\cr}$$
We construct $\omega'$ by

\vskip 1in

If all the diagrams above commute, by case analysis on whether the input state
is $\Lambda$ or starts with character $a$, $\pi'$ simulates $\pi$.  After
$\pi'$ executes {\tt eof}, it remains in states of the form $q . e$; instructions
applicable to such configurations have $\delta$ as the input operation.
Instructions of $\pi'$ factor operations of input away from those of the extra
device; one operation or the other is $\delta$.

The construction of $\pi'$ is straightforward.  If an instruction of $\pi$, say
$\langle q \rightarrow r$, {\rm scan a}, $\varphi\rangle$ appears in the left
column of one of the diagrams above, then any instruction in the right column
must belong to $\pi'$.
\bye